{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Permutations II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: permuteUnique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全排列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个可包含重复数字的序列 <code>nums</code> ，<em><strong>按任意顺序</strong></em> 返回所有不重复的全排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2]\n",
    "<strong>输出：</strong>\n",
    "[[1,1,2],\n",
    " [1,2,1],\n",
    " [2,1,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 8</code></li>\n",
    "\t<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [permutations-ii](https://leetcode.cn/problems/permutations-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [permutations-ii](https://leetcode.cn/problems/permutations-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        seen=set()\n",
    "        self.backtrack(0,nums,res,[],seen)\n",
    "        return res\n",
    "    def backtrack(self,n,nums,res,temp,seen):\n",
    "        if n==len(nums) and temp not in res:\n",
    "            res.append(temp[:])\n",
    "            return \n",
    "        for k in range(0,len(nums)):\n",
    "            if k in seen:\n",
    "                continue\n",
    "            seen.add(k)\n",
    "            temp.append(nums[k])\n",
    "            self.backtrack(n+1,nums,res,temp,seen)\n",
    "            temp.pop()\n",
    "            seen.remove(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        \n",
    "        def backtrack(cnt, cur, ret):\n",
    "            if not cnt:\n",
    "                ret.append(cur)\n",
    "            for num in cnt:\n",
    "                cnt_ = cnt.copy()\n",
    "                if cnt_[num] == 1:\n",
    "                    cnt_.pop(num)\n",
    "                else:\n",
    "                    cnt_[num] -= 1\n",
    "                backtrack(cnt_, cur + [num], ret)\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        ret = []\n",
    "        backtrack(cnt, [], ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        return list(set(itertools.permutations(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def permuteUnique(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        self.result = []\n",
    "        self.used = [False] * len(nums)\n",
    "        nums = sorted(nums)\n",
    "        self.exchange(nums, 0, length=len(nums), temp_result=[])\n",
    "        return self.result\n",
    "\n",
    "    def exchange(self, data, start, length, temp_result):\n",
    "        if len(temp_result) == length:\n",
    "            self.result.append(copy.deepcopy(temp_result))\n",
    "            return None\n",
    "        for i in range(0, length):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "            if i > 0 and data[i] == data[i - 1] and not self.used[i - 1]:\n",
    "                continue\n",
    "            # data = self.swap(data, start, i)\n",
    "            self.used[i] = True\n",
    "            temp_result.append(data[i])\n",
    "            self.exchange(data, start + 1, length, temp_result)\n",
    "            _ = temp_result.pop(-1)\n",
    "            self.used[i] = False\n",
    "            # data = self.swap(data, start, i)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        result.append([])\n",
    "        for i, num in enumerate(nums):\n",
    "            current_result = []\n",
    "            for item in result:\n",
    "                for j in range(i + 1):\n",
    "                    if j > 0 and num == item[j - 1]:\n",
    "                        break\n",
    "                    temp = item[:]\n",
    "                    temp.insert(j, num)\n",
    "                    current_result.append(temp)\n",
    "            result = current_result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        import copy\n",
    "        def dfs(nums, begin, end):\n",
    "            if begin==end:\n",
    "                if nums not in res:\n",
    "                    res.append(copy.copy(nums))\n",
    "            else:\n",
    "                for i in range(begin, end+1):\n",
    "                    nums[i], nums[begin] = nums[begin], nums[i]\n",
    "                    dfs(nums, begin+1, end)\n",
    "                    nums[i], nums[begin] = nums[begin], nums[i]\n",
    "        \n",
    "        length = len(nums)\n",
    "        res = []\n",
    "        dfs(nums, 0, length-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        \n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        \n",
    "        def patch(nums,i):\n",
    "            if i == length:\n",
    "                result.append(nums.copy())\n",
    "                return\n",
    "            \n",
    "            patch(nums,i+1)\n",
    "            \n",
    "            for j in range(i+1,length):\n",
    "                if nums[j] != nums[i] and nums[j] != nums[j-1]:\n",
    "                    tmp = nums[i]\n",
    "                    nums[i] = nums[j]\n",
    "                    nums[j] = tmp\n",
    "\n",
    "                    patch(nums,i+1)\n",
    "\n",
    "                    tmp = nums[i]\n",
    "                    nums[i] = nums[j]\n",
    "                    nums[j] = tmp\n",
    "        \n",
    "        #nums.sort()\n",
    "        patch(nums,0)\n",
    "        b = []\n",
    "        for i in result:\n",
    "            if i not in b:\n",
    "                b.append(i)\n",
    "                \n",
    "        return b\n",
    "                    \n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def ins(sub_nums, num):\n",
    "            combined_nums = []\n",
    "            for i in range(len(sub_nums)+1):\n",
    "                cur_nums = sub_nums[:]\n",
    "                if i < len(cur_nums) and cur_nums[i] == num:\n",
    "                    continue\n",
    "                cur_nums.insert(i, num)\n",
    "                combined_nums.append(cur_nums)\n",
    "            return combined_nums\n",
    "        \n",
    "        anses = [[nums.pop()]]\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            num = nums.pop()\n",
    "            cr = []\n",
    "            for ans in anses:\n",
    "                cr += ins(ans, num)\n",
    "            anses = cr      \n",
    "            \n",
    "            \n",
    "        # 去重\n",
    "        cr = []\n",
    "        for ans in anses:\n",
    "            if ans not in cr:\n",
    "                cr.append(ans)\n",
    "        anses = cr\n",
    "        return anses       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if nums is None:\n",
    "            return []\n",
    "        if len(nums) == 0:\n",
    "            return [[]]\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        visited = [False] * len(nums)\n",
    "        self.dfs(nums, visited, [], res)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, nums, visited, permutation, res):\n",
    "        if len(permutation) == len(nums):\n",
    "            return res.append(permutation[:])\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "                \n",
    "            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:\n",
    "                continue\n",
    "            permutation.append(nums[i])\n",
    "            visited[i] = True\n",
    "            self.dfs(nums, visited, permutation, res)\n",
    "            visited[i] = False\n",
    "            permutation.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        len_nums = len(nums)\n",
    "        if len_nums == 0:\n",
    "            return []\n",
    "        used = [False] *len_nums\n",
    "        nums.sort()\n",
    "        path = []\n",
    "        res = []\n",
    "        self.__dfs(nums,0,path,used,res)\n",
    "        return res\n",
    "\n",
    "    def __dfs(self,nums,count,path,used,res):\n",
    "        if count == len(nums):\n",
    "            res.append(path[:])\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if not used[i]:\n",
    "                if i >0 and nums[i] == nums [i-1] and not used[i-1]:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(nums[i])\n",
    "                self.__dfs(nums,count+1,path,used,res)\n",
    "                used[i] = False\n",
    "                path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 回溯+剪枝\n",
    "        def dfs(nums,size,depth,path,used,res):\n",
    "            if depth==size:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            else:\n",
    "                for i in range(size):\n",
    "                    if not used[i]:\n",
    "                        if i>0 and nums[i]==nums[i-1] and not used[i-1]:\n",
    "                            continue\n",
    "                        path.append(nums[i])\n",
    "                        used[i]=True\n",
    "                        dfs(nums,size,depth+1,path,used,res)\n",
    "                        path.pop()\n",
    "                        used[i]=False\n",
    "                return\n",
    "\n",
    "        size = len(nums)\n",
    "        if not size: \n",
    "            return []\n",
    "        nums.sort()#在原数组上排序\n",
    "        res = []\n",
    "        path = []\n",
    "        used = [False for _ in range(size)]\n",
    "        dfs(nums,size,0,path,used,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums: return\n",
    "        nums=sorted(nums)\n",
    "        res=[]\n",
    "        n=len(nums)\n",
    "        \n",
    "        self.backtrace(nums,res,[],n)\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def backtrace(self,nums,res,re,n):\n",
    "        if len(re)==n:\n",
    "            res.append(re.copy())\n",
    "            return \n",
    "        for i in range(len(nums)):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            re.append(nums[i])\n",
    "            self.backtrace(nums[:i]+nums[i+1:],res,re,n)\n",
    "            re.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums, size, depth, path, used, res):\n",
    "            if depth == size:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(size):\n",
    "                if not used[i]:\n",
    "                    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:  \n",
    "                        continue\n",
    "                    used[i] = True\n",
    "                    path.append(nums[i])\n",
    "                    dfs(nums, size, depth + 1, path, used, res)\n",
    "                    used[i] = False\n",
    "                    path.pop()\n",
    "\n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return []\n",
    "\n",
    "        nums.sort()\n",
    "        used = [False] * len(nums)\n",
    "        res = []\n",
    "        dfs(nums, size, 0, [], used, res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(set(itertools.permutations(nums,len(nums))))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) <= 1:\n",
    "            return [nums]\n",
    "        else:\n",
    "            a = []\n",
    "            for x in list(set(nums)):\n",
    "                i = nums.index(x)\n",
    "                xs = nums[:i] + nums[i+1:]\n",
    "                for p in self.permuteUnique(xs):\n",
    "                    a.append([x] + p)\n",
    "            return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        self._permute(0, nums, res)\n",
    "        return res\n",
    "\n",
    "    def _permute(self, cur_depth, nums, res):\n",
    "        if cur_depth == len(nums)-1:\n",
    "            res.append(copy.copy(nums))\n",
    "            return\n",
    "        print(nums, cur_depth)\n",
    "        visited = set([nums[cur_depth]])\n",
    "        for i in range(cur_depth, len(nums)):\n",
    "            if cur_depth != i and nums[i] in visited:\n",
    "                continue\n",
    "            visited.add(nums[i])\n",
    "            nums[i], nums[cur_depth] = nums[cur_depth], nums[i]\n",
    "            self._permute(cur_depth+1, nums, res)\n",
    "            nums[i], nums[cur_depth] = nums[cur_depth], nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        used = [0 for i in range(len(nums))]\n",
    "        def backtarck(cur,nums,res,used):\n",
    "            if len(cur) == len(nums):\n",
    "                \n",
    "                res.append(cur[:])\n",
    "                return\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == 1 or (i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 1):\n",
    "                    continue\n",
    "                cur.append(nums[i])\n",
    "                used[i] = 1\n",
    "                \n",
    "                backtarck(cur,nums,res,used)\n",
    "\n",
    "                cur.pop()\n",
    "                used[i] = 0\n",
    "        m = backtarck([],nums,res,used)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(i,tmp):\n",
    "            if i==len(nums):\n",
    "                res.append(tmp[:])\n",
    "                return\n",
    "            for j in range(len(nums)):\n",
    "                if check[j]==1:continue\n",
    "                if j>0 and nums[j]==nums[j-1] and check[j-1]==0:continue\n",
    "                check[j]=1\n",
    "                tmp.append(nums[j])\n",
    "                dfs(i+1,tmp)\n",
    "                tmp.pop()\n",
    "                check[j]=0\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        check = [0 for i in range(len(nums))]\n",
    "        dfs(0,[])\n",
    "        return res\n",
    "print(Solution().permuteUnique([0,1,0,0,9]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        lenth = len(nums)\n",
    "        used = [False for i in range(lenth)]\n",
    "        \n",
    "        def dfs(depth,used,path):\n",
    "            if depth == lenth:\n",
    "                if path[:] not in res:\n",
    "                    res.append(path[:])\n",
    "            for i in range(lenth):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                dfs(depth+1,used,path)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "\n",
    "\n",
    "        dfs(0,used,path)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        hashmap,l,res=set(),len(nums),[]\n",
    "        def backtrack(nums,temp=[],depth=0):\n",
    "            if depth==l:\n",
    "                temp=tuple(temp)\n",
    "                if temp not in hashmap:\n",
    "                    res.append(list(temp))\n",
    "                    hashmap.add(temp)\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                backtrack(nums[:i]+nums[i+1:],temp+[nums[i]],depth+1)\n",
    "        backtrack(nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = permutations(nums)\n",
    "        res = list(set(res))\n",
    "        res = map(lambda x: list(x), res)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums,size,depth,path,used,res):\n",
    "            if depth == size:\n",
    "                res.append(path.copy())\n",
    "                return \n",
    "            \n",
    "            for i in range(size):\n",
    "                if not used[i]:\n",
    "                    if i>0 and nums[i]==nums[i-1] and not used[i-1]:\n",
    "                        continue\n",
    "                    #检查前一个元素是否与当前元素相同，如果相同并且前一个元素未被使用，则跳过当前元素。\n",
    "                    \n",
    "                    used[i] = True\n",
    "                    path.append(nums[i])\n",
    "                    #将当前元素标记为已使用，并将其添加到路径 path 中\n",
    "                    dfs(nums,size,depth+1,path,used,res)\n",
    "                    used[i] = False\n",
    "                    path.pop()\n",
    "                    #恢复当前元素的状态并将其从路径 path 中移除。\n",
    "\n",
    "                    #当存在相同元素时，如果之前的那个元素没有被使用，则说明这两个元素在同一层搜索中，应该跳过当前元素，保证搜索的唯一性。\n",
    "        \n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return []\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        used = [False]*len(nums)\n",
    "        #这行代码是初始化一个布尔类型的数组，用于标记 nums 列表中的每个元素是否已经被使用过。\n",
    "        #当一个元素被使用时，将其索引对应的 used 数组中的值标记为 True，表示该元素已经被使用过了。当回溯回来时，将其 used 数组中的值重新标记为 False，以便下次搜索时可以重新使用该元素。\n",
    "        res = []\n",
    "        dfs(nums,size,0,[],used,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 先自己画一颗没剪枝之前的树，看看谁需要被剪枝，就知道了\n",
    "        # 1. 将数组排序，使得相同的树枝值挨在一起。2. 对于一个节点下，相同的树枝值只选择一个，其余剪枝。\n",
    "        # nums = sorted(nums)\n",
    "        self.result = []\n",
    "        self.backtrack([], [], nums)\n",
    "        return self.result\n",
    "        \n",
    "    def backtrack(self, path, path_idx, nums):\n",
    "        # 因为有重复的值，所以额外记录下path的idx\n",
    "\n",
    "        if len(path) == len(nums):\n",
    "            self.result.append(path)\n",
    "            return\n",
    "        \n",
    "        already_choice = []  # 当前节点已经选择过的路径值，用来剪枝\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx not in path_idx and (num not in already_choice):\n",
    "                already_choice.append(num)\n",
    "                self.backtrack(path+[num], path_idx+[idx], nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 先自己画一颗没剪枝之前的树，看看谁需要被剪枝，就知道了\n",
    "        # 1. 将数组排序，使得相同的树枝值挨在一起。2. 对于一个节点下，相同的树枝值只选择一个，其余剪枝。\n",
    "        nums = sorted(nums)\n",
    "        self.result = []\n",
    "        self.backtrack([], [], nums)\n",
    "        return self.result\n",
    "        \n",
    "    def backtrack(self, path, path_idx, nums):\n",
    "        # 因为有重复的值，所以额外记录下path的idx\n",
    "\n",
    "        if len(path) == len(nums):\n",
    "            self.result.append(path)\n",
    "            return\n",
    "        \n",
    "        already_choice = []  # 当前节点已经选择过的路径值，用来剪枝\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx not in path_idx and (num not in already_choice):\n",
    "                already_choice.append(num)\n",
    "                self.backtrack(path+[num], path_idx+[idx], nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一回溯但时间长\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def permuteUnique(self, nums: List[int]):\r\n",
    "        def backtrack(first: int):\r\n",
    "            if first == n and nums[:] not in res: # 这句判断花费很多时间\r\n",
    "                res.append(nums[:])\r\n",
    "            for i in range(first, n):\r\n",
    "                nums[first], nums[i] = nums[i], nums[first]\r\n",
    "                backtrack(first + 1)\r\n",
    "                nums[first], nums[i] = nums[i], nums[first] # 回溯即重置状态\r\n",
    "        n = len(nums)\r\n",
    "        res = []\r\n",
    "        backtrack(0)\r\n",
    "        return res\r\n",
    "'''\r\n",
    "# 方法二回溯用了剪枝,时间短\r\n",
    "class Solution:\r\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\r\n",
    "        def backtrack(sol: list, nums: list, visited: list):\r\n",
    "            if len(sol) == len(nums):\r\n",
    "                res.append(sol)\r\n",
    "\r\n",
    "            for i in range(len(nums)):\r\n",
    "                if visited[i] == 1:\r\n",
    "                    continue\r\n",
    "                if i > 0 and nums[i - 1] == nums[i] and visited[i - 1] == 0:\r\n",
    "                    continue\r\n",
    "                visited[i] = 1\r\n",
    "                backtrack(sol + [nums[i]], nums, visited)\r\n",
    "                visited[i] = 0\r\n",
    "        \r\n",
    "        nums.sort()\r\n",
    "        res = []\r\n",
    "        visited = [0 for _ in range(len(nums))]\r\n",
    "        backtrack([], nums, visited)\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一回溯但时间长\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def permuteUnique(self, nums: List[int]):\r\n",
    "        def backtrack(first: int):\r\n",
    "            if first == n and nums[:] not in res: # 这句判断花费很多时间\r\n",
    "                res.append(nums[:])\r\n",
    "            for i in range(first, n):\r\n",
    "                nums[first], nums[i] = nums[i], nums[first]\r\n",
    "                backtrack(first + 1)\r\n",
    "                nums[first], nums[i] = nums[i], nums[first] # 回溯即重置状态\r\n",
    "        n = len(nums)\r\n",
    "        res = []\r\n",
    "        backtrack(0)\r\n",
    "        return res\r\n",
    "'''\r\n",
    "# 方法二回溯用了剪枝\r\n",
    "class Solution:\r\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\r\n",
    "        def backtrack(sol: list, nums: list, visited: list):\r\n",
    "            if len(sol) == len(nums):\r\n",
    "                res.append(sol)\r\n",
    "                return\r\n",
    "            for i in range(len(nums)):\r\n",
    "                if visited[i] == 1:\r\n",
    "                    continue\r\n",
    "                if i > 0 and nums[i - 1] == nums[i] and visited[i - 1] == 0:\r\n",
    "                    continue\r\n",
    "                visited[i] = 1\r\n",
    "                backtrack(sol + [nums[i]], nums, visited)\r\n",
    "                visited[i] = 0\r\n",
    "        \r\n",
    "        nums.sort()\r\n",
    "        res = []\r\n",
    "        visited = [0 for _ in range(len(nums))]\r\n",
    "        backtrack([], nums, visited)\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums)==1:\n",
    "            return [nums]\n",
    "        t=[]\n",
    "        m=nums[0]\n",
    "        nums.pop(0)\n",
    "        for i in self.permuteUnique(nums):\n",
    "            for j in range(len(nums)+1):\n",
    "                i.insert(j,m)\n",
    "                if i not in t:\n",
    "                    t.append(i[:])\n",
    "                i.pop(j)\n",
    "        nums.insert(0,m)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        used = [False]*len(nums)\n",
    "        def backtracking(res,path,used):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if (i>0 and nums[i] == nums[i-1] and used[i-1]==True) or used[i]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                backtracking(res,path,used)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        backtracking(res,[],used)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []\n",
    "        path = []\n",
    "        used = [0] * len(nums)\n",
    "        self.backtrack(nums,used,path,result)\n",
    "        return result\n",
    "    \n",
    "    def backtrack(self,nums,used,path,result):\n",
    "        if len(path) == len(nums) and path not in result:\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if used[i] == 1:\n",
    "                continue\n",
    "            path.append(nums[i])\n",
    "            used[i] = 1\n",
    "            self.backtrack(nums,used,path,result)\n",
    "            path.pop()\n",
    "            used[i] = 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        def dfs(path,candidates,used):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "            for i in range(len(candidates)):\n",
    "                if i > 0 and candidates[i] == candidates[i-1] and not used[i-1]:\n",
    "                    continue\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i] = True \n",
    "                path.append(candidates[i])\n",
    "                dfs(path,candidates,used)\n",
    "                used[i] = False\n",
    "                path.pop() \n",
    "        dfs([], nums, [False]*len(nums))\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
